import { TreeNode } from '../base/tree-node';

/**
 * 向二叉搜索树中插入节点
 * @param root 二叉搜索树的根节点
 * @param value 要插入的值
 */
export function insertIntoBST(root: TreeNode, value: number): void {
  if (value < root.val) {
    if (!root.left) {
      root.left = new TreeNode(value);
    } else {
      insertIntoBST(root.left, value);
    }
  } else {
    if (!root.right) {
      root.right = new TreeNode(value);
    } else {
      insertIntoBST(root.right, value);
    }
  }
}

/**
 * 从数组构建二叉搜索树
 * @param values 用于构建树的数组
 * @returns 构建好的二叉搜索树的根节点
 */
export function buildBSTFromArray(values: number[]): TreeNode | null {
  if (!values.length) return null;

  const root = new TreeNode(values[0]);

  for (let i = 1; i < values.length; i++) {
    insertIntoBST(root, values[i]);
  }

  return root;
}

/**
 *
 * 递归验证二叉搜索树
 * @param root 二叉搜索树的根节点
 * @returns 如果是二叉搜索树则返回true，否则返回false
 */
// 递归验证二叉搜索树
export function validateBST(root: TreeNode | null): boolean {
  function dfs(node: TreeNode | null, min: number, max: number): boolean {
    if (!node) return true;
    // 允许重复值出现在右子树：左子树必须严格小于，右子树可以大于等于
    if (node.val < min || node.val >= max) return false;
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
  }
  return dfs(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
}
